package com.dragon.datastructure.sort;

/**
 * 选择排序
 * <p>
 * 每一个外圈循环拿出一个元素与数组中余下的元素进行比较，找到最小的元素，之后在外圈与arr[i]交换位置
 * <p>
 * 选择排序是外循环交换位置，只需要记录最小的角标，之后在外循环进行交换，而冒泡排序则是在内循环进行交换
 * <p>
 * 基于数组元素大多数情况下都是无序的，所以选择排序的效率是要高于冒泡排序
 *
 * @author dragon
 * @since 2019/12/23
 */
public class SelectSort {

    public static void main(String[] args) {
        // 选择排序耗费的时间:8196毫秒
        Integer[] array = new Integer[80_000];
        for (int i = 0; i < array.length; i++) {
            array[i] = (int) (Math.random() * 800_000);
        }
        long startTime = System.currentTimeMillis();
        sort(array);
        long entTime = System.currentTimeMillis();
        System.out.println("选择排序耗费的时间:" + (entTime - startTime) + "毫秒");
    }

    /**
     * 选择排序
     *
     * @param source 被排序的数组
     * @param <T>    数组中的元素类型
     */
    public static <T extends Comparable<T>> void sort(T[] source) {
        if (source == null) {
            return;
        }
        for (int i = 0; i < source.length - 1; i++) {
            T min = source[i];
            int minIndex = i;
            for (int j = i + 1; j < source.length; j++) {
                if (min.compareTo(source[j]) > 0) {
                    min = source[j];
                    minIndex = j;
                }
            }
            if (minIndex != i) {
                source[minIndex] = source[i];
                source[i] = min;
            }
        }
    }
}
